#ifndef _DYNAMICARRAY2_H_
#define _DYNAMICARRAY2_H_
#include <stddef.h>
#include <limits.h>

using ElementType = int;

class DynamicArray
{
public:
    DynamicArray(size_t capacity = 15);
    DynamicArray(const DynamicArray& a);
    DynamicArray& operator=(const DynamicArray& a);
    ~DynamicArray();

    size_t Size();
    void ReSize(size_t capacity); //修改数组容量，可变大变小

    void InsertTail(const ElementType& element); //尾插
    void InsertHead(const ElementType& element);//头插
    void InsertByIndex(int index,const ElementType& element);//中间插

    void RemoveByIndex(int index);//按下标删除
    void RemoveByElement(const ElementType& element);//按值删除

    ElementType* FindByIndex(int index);//按位置查找,返回的是值
    //按值查找因为找到的可能不止一个，所以返回数组
    DynamicArray FindByElement(const ElementType& element);

    void UpdateByIndex(int index,const ElementType& element);//按下标修改
    void UpdateByElement(const ElementType& oldValue,const ElementType& newValue);//按值修改
    
    void Sort();

    void Duplicate(); //去重

    DynamicArray Merge(const DynamicArray& a); //和并

    DynamicArray FdInterSctn(const DynamicArray& a);//找交集
    DynamicArray FdUnionSet(const DynamicArray& a);//找并集
    DynamicArray FdDiffernce(const DynamicArray& a);//找补集

    bool operator==(const DynamicArray& a); // 判断是否相等

    size_t BinarySearch(const ElementType& element);//二分

    bool IsChild(const DynamicArray& a); //是不是子数列
    bool IsContinueChild(const DynamicArray& a);//连续子数列
    DynamicArray subsequence(int index,size_t size); //获取子序列

    void show();
private:
    void FastSort(size_t start,size_t end,size_t deepth,size_t MaxDepth); //快速排序
    void InsertSort(size_t start,size_t end); //插入排序
    size_t Partition(size_t start,size_t end); //分组函数

    ElementType *array;
    size_t size;
    size_t capacity;
};

#endif